Name: 3-Satisfiability (3-SAT) [LO2] 2

Input: A set of m clauses - C₁ ,C₂,...,C_m - over a set of n Boolean valued variables X_n=< x₁,x₂,...,x_n>, such that each clause depends on exactly three distinct variables from X_n. A clause being a Boolean expression of the form y_i+y_j+y_k where each y is of the form x or -x (i.e. negation of x) with x being some variable in X_n. For example if n=4 and m=3 a possible instance could be the (set of) Boolean expressions: C₁=(x₁+(-x₂)+(-x₃)); C₂=(x₂+x₃+(-x₄)); C₃=((-x₁)+x₃+x₄);

Question: Can each variable x_i of X_n be assigned a Boolean value alpha_i in such a way that every clause evaluates to the Boolean result true under the assignment < x_i:=alpha_i:1<=i<=n>?

In the example instance, the assignment < x₁:=true;x₂:=false;x₃:=true; x₄:=false> is such that each of the three clauses takes the value true.

Comments: For reasons that will become clearer at the end of the course, this problem had to be Number 1. Some relevant material concerning this problem might be found in the special issue (Volume 81, 1996) of the journal Artificial Intelligence that is available in the Library.

Name: Graph 3-Colourability (3-COL) [GT4] 1

Input: An n-node undirected graph G(V,E) with node set V and edge set E.

Question: Can each node of G(V,E) be assigned exactly one of three colours - Red, Blue, Green - in such a way that no two nodes which are joined by an edge, are assigned the same colour?

Name: Monochromatic triangle [GT6] 2

Input: An n-node undirected graph G(V,E) with node set V and edge set E.

Question: Can the edges, E, of G be partitioned into two disjoint sets E₁ and E₂, in such a way that neither of the two graphs G₁(V,E₁) or G₂(V,E₂) contains a triangle, i.e. a set of three distinct nodes u,v,w such that {u,v}, {u,w}, {v,w} are all edges?

Name: Clique [GT19] 1

Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=n.

Question: Does G contain a k-clique, i.e. a subset W of the nodes V such that W has size k and for each distinct pair of nodes u, v in W, {u,v} is an edge of G?

Name: Bipartite Subgraph [GT25] 2

Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=|E|.

Question: Is there a subset, F of the edges of G, having size at least k and such that the graph H(V,F) is bipartite?

Comments: G(V,E) is bipartite if the nodes can be partitioned into two disjoint sets U and W such that every edge of G connects a node in U to a node in W, i.e. no two nodes in U (resp. W) form an edge of G.

Name: Vertex Cover [GT1] 1

Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=n.

Question: Is there a subset W of V having size at most k and such that for every edge {u,v} in E at least one of u and v belongs to W?

Name: Chromatic Index (Edge Colouring) [OPEN5] 3

Input: An n-node undirected graph G(V,E) with node set V and edge set E; a positive integer k with k<=|E|.

Question: Can the edges of G be assigned exactly one of k colours in such a way that no two edges which have a common node as an endpoint are assigned the same colour?

Comments: Vizing's Theorem from Graph Theory shows that the only `hard' case for this problem is when k is equal to the maximum degree of G. The degree of a node, v, is the number of edges in the graph with v as an end-point; the degree of a graph is the maximum degree of any node in the graph. Chromatic Index was shown to be NP-complete soon after the 1979 edition of Garey and Johnson went to press, hence the OPEN categorisation.

The classical paper on sequential methods is:

Name: Multiprocessor Scheduling [SS8] 4

Input: A set, T, of tasks and for each task t in T a positive (integer) running time len(t). A positive integer D, called the deadline.

Question: Is there a 2-processor schedule for the tasks that completes within the deadline, D, i.e. is there a function sigma:T->N such that both of the following hold:

• For all u>=0 the number of tasks t in T for which sigma(t)<=u< sigma(t)+len(t) is at most 2.
• For all tasks t, sigma(t)+len(t)<=D?

Name: Comparative Divisibility [AN4] 3

Input: A (strictly increasing) sequence A=< a₁,a₂,...,a_n> and a (strictly increasing) sequence B=< b₁,b₂,...,b_m> of positive integers.

Question: Is there an integer, c, such that Divides(c,A)> Divides(c,B), where Divides(x,Y) (Y being a sequence of positive integers) is the number of elements, y in Y, for which x is an exact divisor of y?

Comments: You may think that this has an obvious fast algorithm, and, indeed the algorithm in question is obvious: what it is not is efficient. Consider: how many bits are needed to store the input data (assuming, without loss of generality, that a_n>=b_m)? How many steps, however, is this `obvious method' taking in the worst-case? It is important to realise that representing integer values in unary is not considered to be a `reasonable' approach (the number 2⁵⁰-1 requires 2⁵⁰ digits in unary but only 50 digits in binary).

Name: Cyclic Ordering [MS2] 3

Input: A finite set, A, and a collection, C, of ordered triples (a,b,c) of distinct elements from A.

Question: Is there a one-to-one mapping f:A->{1,2,3,...,|A|} (i.e. a function which maps each element of A to a number between 1 and |A| with no two distinct elements of A being mapped to the same number) such that for each (a,b,c) in C one of

f(a) < f(b) < f(c) ; f(b) < f(c) < f(a) ; f(c) < f(a) < f(b)

holds?

Comments: For any triple (a,b,c) there are 6 (six) possible orderings that could result for ((a),f(b),f(c)). The question being asked is whether there is a choice of function that forces every specified triple into one of three `legal' orderings. Garey and Johnson has a typographical error in describing this problem, whereby each triple `in A' is referred to. Obviously `in C' is intended.

Name: Quadratic Diophantine Equations [AN8] 3

Input: Positive integers a, b, and c.

Question: Are there two positive integers x and y such that (a*x*x)+(b*y)=c?

Name: Maximum 2-Satisfiability [LO5] 3

Input: A set of m clauses C₁,C₂,...,C_m over n Boolean valued variables X_n, where each clause depends on two distinct variables from X_n; a positive integer k with k<=m.

Question: Is there an assignment of Boolean values to the variables X_n such that at least k distinct clauses take the value true under the assignment?

Name: Register Sufficiency [PO1] 5

Input: A directed, acyclic graph G(V,A) in which each node has at most two out-going edges; a positive integer k.

Question: Is there a k or fewer register `computation' for G, i.e. is there an ordering < v₁,v₂,...,v_n> of the (n) nodes of G and a sequence < S₀;S₁;...;S_n> of subsets of V which satisfy all of the following:

• For all i, S_i contains at most k nodes from V.
• S₀ contains no nodes; S_n contains all of the nodes in V with no in-coming edges in G (recall that G is directed).
• For each i, with 1<=i<=n: v_i is in S_i; S_i-{v_i} is a subset of the nodes in S_i-1; and S_i-1 contains all nodes u for which (v_i,u) is an edge in A, i.e. all nodes, u, for which there is an edge from v_i to u?

Comments: The background to this problem comes from developing Code Generation methods in compilers for High-Level Languages. On early architectures, performing arithmetic operations with both operands stored in registers was significantly faster than fetching an operand from main memory. Such machines, however, had only a small (16-32) number of fast registers. Thus in generating assembly code to represent the computation of a lengthy arithmetic expression, it was necessary to use registers efficiently. A common first stage in compiling such expressions was to represent the computation as a (so-called) `straight-line program' which in turn could be modelled as a directed acyclic graph. The object of the Register Sufficiency Problem is to determine if such a `straight-line program' can be evaluated using only the specified number of available registers.

Name: Central Slice of Half-Clique 2

Input: An 2n-node undirected graph G(V,E) with node set V and edge set E.

Question: Does either of the following hold true of G(V,E)

• G contains at least (2n²-n)/2+1 edges.
• G contains exactly (2n²-n)/2 edges and G contains an n-clique?

Name: Decision Tree [MS15] 5

Input: A Boolean logic function, f, of n variables, X_n, described by its 1-points, i.e. the set of assignments, alpha=< a₁,...,a_n> such that f(a₁,...,a_n)=1; a positive integer K.

Question: Is there a decision tree for f that has average path length at most K?

Comments: A decision tree is a binary tree in which each non-leaf node is labelled with a variable from X_n, each leaf node is labelled either 0 or 1, the edge from a non-leaf node to its left child is labelled 0, that to its right child is labelled 1. For a given assignment of Boolean values to the variables X_n a path can be traced starting from the root of the decision tree and following the edges marked with the value of the variable labelling each node encountered. The path terminates at a leaf node whose associated label gives the value of the function. The decision tree computes a Boolean function f(X_n) if for every assignment, alpha, to the variables the path traced from the root under alpha terminates in a leaf labelled f(alpha). The average path length of a binary tree with t leaf nodes and root v is: sum from {w:w is a leaf} |Path from x to w|/t.

This problem is a simpler (but still NP-complete) version of the form given in Garey and Johnson. For relevant variations and potential heuristic approaches, the papers

Name: Shortest Common Superstring [SR9] 3

Input: A finite set R={r₁,r₂,...,r_m} of binary strings (sequences of 0 and 1); positive integer k.

Question: Is there a binary string w of length at most k such that every string in R is a substring of w, i.e. for each r in R, w can be decomposed as w=w₀rw₁ where w₀, w₁ are (possibly empty) binary strings?

Comments: General problem allows more than two symbols (i.e. not just binary), but this simpler version remains NP-complete.

Name: Longest Circuit [ND28] 2

Input: n-node undirected graph G(V,E); positive integer k.

Question: Does G contain a simple cycle containing at least k nodes?

Name: Kernel [GT57] 2

Input: n-node directed graph G(V,A).

Question: Does G possess a kernel, i.e. a subset W of the nodes V such that no two nodes in W are joined by an edge in A and such that for each node v in V-W there is a node w in W for which (w,v) is an edge in A?

Name: k-Closure [GT58] 2

Input: n-node directed graph G(V,A); positive integer k<=n.

Question: Is there a subset W of V having size at most k and such that for all edges (u,v) in A either u is in W or v is not in W.

Name: Bandwidth [GT40] 3

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Is there a linear ordering of V with bandwidth at most k, i.e. a one-to-one function f:V->{1,2,...,n} such that for all edges {u,v} in G, |f(u)-f(v)|<=k?

Name: Maximum Leaf Spanning Tree [ND2] 4

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Does G have a spanning tree in which at least k nodes have degree 1.

Name: Independent Set [GT20] 1

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Does G have an independent set of size at least k, i.e. a subset W of at least k nodes from V such that no pair of nodes in W is joined by an edge in E?

Name: Degree Constrained Spanning Tree [ND1] 4

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Does G have a spanning tree in which no node has degree greater than k?

Name: Hamiltonian Path [GT39] 1

Input: n-node undirected graph G(V,E).

Question: Is there a simple path of edges in G that contains every node in V, and thus contains exactly n-1 edges?

Name: Graph Partitioning [ND14] 2

Input: 2n-node undirected graph G(V,E); positive integer k<=|E|.

Question: Can the nodes of G be partitioned into 2 disjoint sets U and W each of size n and such that the total number of distinct edges in E that connect a node u in U to a node w in W is at most k?

Name: Cubic Subgraph [GT32] 3

Input: n-node undirected graph G(V,E).

Question: Is there a (non-empty) subset F of the edges of G such that every node in the graph H(V,F) has either degree 3 or degree 0.

Name: Travelling Salesman [ND22] 3-4

Input: A set C of n cities {c₁,...,c_n}; for each pair of cities (c_i,c_j) (1<=i< j<=n) a positive integer distance d_i,j; a positive integer B.

Question: Is there an ordering < pi(1),pi(2),...,pi(n)> of the n cities such that the value sum from i=1 to n-1 d_{pi(i),pi(i+1)}+d_pi(n),pi(1) is no more than B?

Name: Steiner Tree in Bipartite Graphs [ND12a] 3

Input: Bipartite graph B(V,W,E); positive integer k.

Question: Is there a subtree of B(V,W,E) that includes all of the nodes of V and has at most k edges?

Name: Bounded Diameter Spanning Tree [ND4] 4

Input: n-node undirected graph G(V,E); for each edge, {u,v} a positive integer weight w(u,v); positive integer B.

Question: Does G have a spanning tree T such that the total sum of the weights of edges in T is at most B and no simple path in T contains more than 5 edges?

Name: Optimal Linear Arrangement [GT42] 3

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Is there a one-to-one function f:V->{1,2,...,n} such that sum from {{u,v} in E} |f(u)-f(v)|<=K?

Name: Dominating Set [GT2] 2

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Does G contain a dominating set of size at most k, i.e. a subset W of V containing at most k nodes and such that for every node u in V-W (i.e. in V but not in W) there is a node w in W such that {u,w} is an edge of G?

Name: Path with Forbidden Pairs [GT54] 4

Input: n-node directed graph G(V,A); two distinct nodes s and t belonging to V; finite collection C={(a₁,b₁),...,(a_r,b_r)} of pairs of nodes from V.

Question: Is there a directed path from the node s to the node t in G that contains at most one node from each pair of nodes in the collection C?

Comments: Several simplifications of this problem remain NP-complete: requiring G to be acyclic; requiring the collection C to contain only directed edges from A (rather than arbitrary pairs of nodes); requiring all the pairs to be disjoint.

Name: Oriented Diameter [GT64] 4

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Can a direction be placed on each edge {u,v} of E in such a way that the resulting directed graph H(V,A) is such that both of the following hold:

• H(V,A) is strongly connected, i.e. for each distinct pair of nodes, v and w, there exists a directed path from v to w in H and a directed path from w to v in H.
• The diameter of H(V,A) is at most k, i.e. for every pair of nodes v and w, there is a path of at most k edges from v to w and a path of at most k edges from w to v?

Name: Rural Postman [ND27] 3-4

Input: n-node undirected graph G(V,E); subset F of the edges E; positive integer k<=|E|

Question: Is there a (not necessarily simple) cycle of in G that contains every edge in F and has at most k edges in total?

Comments: A simple cycle in a graph is one in which each node visited in the cycle is visited exactly once. A non-simple cycle allows nodes to be visited more than once (although, obviously, each edge can only occur once). For example in the 5 node graph with edges ({1,2};{1,3};{1,4};{1,5};{2,3};{2,4};{2,5};{3,4}), the cycle 1-> 2-> 3-> 1 is a simple cycle; the cycle 1-> 2-> 4-> 3-> 2-> 5-> 1 is a non-simple cycle since 2 is visited twice (notice that in neither case is any edge used more than once).

Name: Longest Path [ND29] 2

Input: n-node undirected graph G(V,E); nodes s and t in V; positive integer k.

Question: Is there a simple path between s and t in G that contains at least k edges?

Name: 3-Dimensional Matching (3DM) [SP1] 3

Input: 3 disjoint sets X, Y, and Z each comprising exactly n elements; a set M of m triples {(x_i,y_i,z_i):1<=i<=m} such that x_i is in X, y_i in Y, and z_i in Z, i.e. M is a subset of XxYxZ.

Question: Does M contain a matching, i.e. is there a subset Q of M such that |Q|=n and for all distinct pairs of triples (u,v,w) and (x,y,z) in Q it holds that u/=x and v/=y and w/=z.

Comments: The variant 2-dimensional matching in which 2 disjoint sets X and Y form the basis of a set of pairs, can be solved by a number of fast methods.

Name: Set Splitting [SP4] 3

Input: A finite set S; A collection C₁,...,C_m of subsets of S.

Question: Can S be partitioned into two disjoint subsets - S₁ and S₂ - such that for each set C_i it holds that C_i is not a subset of S₁ and C_i is not a subset of S₂?

Name: Set Packing [SP3] 3

Input: A collection C=(C₁,...,C_m) of finite sets; a positive integer k<=m.

Question: Are there k sets - D₁,...,D_k - from the collection C such that for all 1<=i< j<=k, D_i and D_j have no common elements?

Name: Exact Cover by 3-Sets (X3C) [SP2] 3

Input: A finite set X containing exactly 3n elements; a collection C of subsets of X each of which contains exactly 3 elements.

Question: Does C contain an exact cover for X, i.e. a sub-collection of 3-element sets D=(D₁,...,D_n) such that each element of X occurs in exactly one subset in D?

Name: Minimum Cover [SP5] 3-4

Input: A finite set S; A collection C=(C₁,...,C_m) of subsets of S; a positive integer k<=m.

Question: Does C contain a cover for S comprising at most k subsets, i.e. a collection D=(D₁,...,D_t), where t<=k, each D_i is a set in C, and such that every element in S belongs to at least one set in D?

Name: Partition [SP12] 3

Input: Finite set A; for each element a in A a positive integer size s(a).

Question: Can A be partitioned into 2 disjoint sets A₁ and A₂ in a such a way that the sum of the sizes s(x) of elements x in A₁ is exactly the same as the sum of the sizes s(y) of the elements y in A₂.

Comments: It should be noted that it is not required that A₁ and A₂ contain equal numbers of elements, although even with this condition the problem is still NP-complete.

Name: Subset Sum [SP13] 3

Input: Finite set A; for each element a in A a positive integer size s(a); a positive integer K.

Question: Is there a subset B of A such that the sum of the sizes, s(x), of the elements x in B is exactly equal to K?

Name: Comparative Containment [SP10] 4

Input: A finite set X; 2 collections R=(R₁,...,R_k) and S=(S₁,...,S_m) each of which is a set of subsets of X; for each R_i in R, a positive integer weight w(R_i); for each S_i in S a positive integer weight w(S_i);

Question: Is there a subset Y of X such that: if R_Y is the set of subsets, R_i of R having Y as a subset of R_i and S_Y is the set of subsets, S_i of S having Y as a subset of S_i then the total weight of the sets in R_Y is at least the total weight of the sets in S_Y.

Name: Minimum Test Set [SP6] 3

Input: A finite set S; A collection C=(C₁,...,C_m) of subsets of S; a positive integer k<=m.

Question: Is there a sub-collection D=(D₁,...,D_t) of the sets in C such that: t<=k and for each distinct pair of elements u, v in S there is a set D_u,v in D that contains exactly one of u and v?

Name: Minimum Sum of Squares [SP19] 3-4

Input: A set A of n elements; for each element a in A a positive integer size s(a); positive integers k<=n and J.

Question: Can A be partitioned into k disjoint sets A₁,...,A_k such that sum from i=1 to k ( sum from {x in A_i} s(x))²<=J?

Name: 3-Partition [SP15] 3

Input: A set A of 3m elements; a positive integer bound B; for each element x in A a positive integer size s(x) that satisfies B/4< s(x)< B/2, and is such that the sum of the sizes of elements in A is exactly mB.

Question: Can A be partitioned into m disjoint sets A₁,...,A_m such that each A_i contains exactly 3 elements of A and each A_i has total size equal to B?

Name: Subset Product [SP14] 3

Input: Finite set A; for each element a in A a positive integer size s(a); a positive integer K.

Question: Is there a subset B of A such that the product (i.e. result of multiplying together all) of the sizes, s(x), of the elements x in B is exactly equal to K?

Name: Bin Packing [SR1] 3

Input: A finite set U of m items; for each item u in U a positive integer size s(u); positive integers B (called the bin capacity) and k<=m.

Question: Can U be partitioned into k disjoint sets U₁,...,U_k such that for each U_i (1<=i<=k) the total sum of the sizes of the items in U_i does not exceed B?

Name: Hitting String [SR12] 3

Input: Finite set S={s¹,...,s^m} each sⁱ being a string of n symbols over {0,1,*}.

Question: Is there a binary string x=x₁x₂...x_n of length n such that for each s^j in S, s^j and x agree in at least one position.

Name: Rectilinear Picture Compression [SR25] 4-5

Input: An n by n matrix M of 0s and 1s; a positive integer K.

Question: Can all of the 1-valued entries in M be covered by a collection of K or fewer rectangles, i.e. is there a sequence of 4-tuples (a_i,b_i,c_i,d_i) (where for all 1<=i<=K, a_i<=b_i and c_i<=d_i) such that:

• For each pair (i,j) (1<=i,j<=n) M[i,j]=1 if and only if for some k (1<=k<=K) it holds that a_k<=i<=b_k and c_k<=j<=d_k?

Comments: Despite the apparently complicated definition, this is quite a well-motivated problem. Its background is, as its name suggests, from image compression and the task being set can be interpreted as representing a 2-dimensional image using at most K `blocks' of information.

Name: Sequencing with Release Times and Deadlines [SS1] 4-5

Input: A set T of tasks; for each task t in T: a positive integer length len(t); a positive integer release time r(t); and a positive integer deadline d(t).

Question: Is there a one-processor schedule for the tasks, T, that satisfies the release time constraints and meets all of the deadlines, i.e. a one-to-one function sigma from the set of tasks to positive integers such that all of the following hold:

• For any two distinct tasks t and w if sigma(t)> sigma(w) then sigma(t)>=sigma(w)+len(w).
• For all tasks t in T, sigma(t)>=r(t).
• For all tasks t in T, sigma(t)+len(t)<=d(t)?

Name: Precedence Constrained Scheduling [SS9] 3-4

Input: A set T of tasks each of which has length 1 or length 2; a partial ordering << on the set of tasks, T; a positive integer deadline D.

Question: Is there a 2-processor schedule, sigma, for T that meets the overall deadline D and obeys the `precedence constraints' of the partial order <<, i.e. if t<< w then sigma(w)>=sigma(t)+len(t)?

Name: Quadratic Congruences [AN1] 3

Input: Positive integers a, b, and c.

Question: Is there a positive integer x whose value is less than c and is such that x²==a(mod b), i.e. the remainder when x² is divided by b is equal to a?

Name: Square-Tiling [GP13] 5

Input: A set C of n `colours'; a collection of tiles, T, each tile t being a 4-tuple < a,b,c,d> of colours where a is the colour at the top of the tile; b that on the right-hand side; c that at the bottom; and d that on the left-hand side of the tile; a positive integer k<=n.

Question: Is there a proper tiling of a k by k square using the tiles in T, i.e. an assignment of a tile A(i,j) in T to each ordered pair (i,j) with 1<=i<=k, 1<=j<=k such that both of the following hold:

• If A(i,j)=< a,b,c,d> and A(i+1,j)=< e,f,g,h> then the colours b and h are identical.
• If A(i,j)=< a,b,c,d> and A(i,j+1)=< e,f,g,h> then the colours c and e are identical?

Comments: Informally, a proper tiling is one in which two tiles which are next to each other are required to have the same colour on touching sides, i.e. the right-hand side of one is coloured the same as the left-hand side of its neighbour and similarly with vertically adjacent tiles: the lower side of one is coloured the same as the top side of its neighbour. Decision problems involving questions about tiling patterns tend to be extremely difficult. For the most general form of the question it can be proven that no algorithm at all exists to solve it, i.e. not even an extremely inefficient one. A tiling problem also constitutes the only known `natural' `hard' member of the following class of problems: given a positive integer n as input, determine the number of `objects' of `size' n having a particular property, e.g. the number of n-node graphs, or the number of n-node graphs with a Hamiltonian circuit.

Name: Crossword Puzzle Construction [GP14] 5

Input: A finite set of characters SIGMA={sigma₁,...,sigma_k}; a finite set, W={w₁,...,w_2n} each w_i being a sequence of n characters from SIGMA, i.e. a string.

Question: Can an n by n crossword puzzle be built using all of the 2n words (strings) in W, i.e. if C is an n by n table of `blanks', is there an assignment, f, that maps each entry (i,j) of C to some character in SIGMA in such a way that the word formed by taking the n consecutive characters in a row corresponds to a word in W; the word formed by taking the n consecutive characters in a column (reading from top-to-bottom) corresponds to a word in W?

Comments: The definition may look complicated but it isn't. Here is a simple example instance for which a crossword can be constructed. Let SIGMA={A,B,C,D,E,G,O}, n=3, and W={AGE,AGO,BEG,CAB,CAD,DOG}. A 3 by 3 crossword puzzle for this is given by the assignment C(1,1)=C; C(1,2)=A; C(1,3)=B; C(2,1)=A; C(2,2)=G; C(2,3)=E; C(3,1)=D; C(3,2)=O; C(3,3)=G. This results in the grid

CAB
AGE
DOG

whose correctness is self-evident.

Name: Disjunctive non-tautology [LO8] 2

Input: A A set of m products - P₁,P₂,...,P_m - over a set of n Boolean valued variables X_n=< x₁,x₂,...,x_n>, such that each product depends on exactly three distinct variables from X_n. A product being a Boolean expression of the form y_i AND y_j AND y_k where each y is of the form x or -x (i.e. negation of x) with x being some variable in X_n.

Question: Is there an assignment of Boolean values to the variables in X_n that results in every product taking the value false (equivalently 0)?

Name: Simultaneous incongruences [AN2] 3

Input: A set of n ordered pairs of positive integers {(a₁,b₁),...,(a_n,b_n)} where a_i<=b_i for each 1<=i<=n.

Question: Is there a positive integer x such that: for each i, a_i does not equal the remainder when dividing x by b_i?

Name: Betweenness [MS1] 3

Input: A finite set of size n, A; a set C of ordered triples, (a,b,c), of distinct elements from A.

Question: Is there a one-to-one function, f:A->{1,2,...,n} such that for each triple (a,b,c) in C it holds that either f(a)< f(b)< f(c) or f(c)< f(b)< f(a)?

Name: Minimum weight and/or graph solution [MS16] 4-5

Input: A directed acyclic graph G(V,A) having a single node s, with no incoming edges; a labelling, f(v) of each node having at least one out-going edge in G, as either an and-node or an or-node; a positive integer K.

Question: Is there a sub-graph H(W,B) of G(V,A), i.e. W is a subset of V and B is a subset of A satisfying all of the following:

• s is in W.
• If w is in W and w is an and-node then all of the edges directed out of w in G belong to B.
• If w is in W and w is an or-node then at least one of the edges directed out of w in G belongs to B.
• B contains at most K edges?

Name: Fault-detection in directed graphs. [MS18] 3-4

Input: A directed, acyclic graph G(V,A) such that G has a unique node t with no out-going edges; I the set of nodes in V having no incoming edges; a positive integer K.

Question: Is there a `test set' of size at most K that can detect every `single fault' in G (N.B. not `every single fault' but every `single fault'), i.e. a subset T of the nodes in I such that

• T contains at most K nodes.
• For every node v in V there exists a node u in T such that v lies on a directed path from u to t in G?

Name: Minimum Broadcast Time. [ND49] 3-4

Input: n-node undirected graph G(V,E); a subset V₀ of the nodes in V.

Question: Can a message be `broadcast' from the base set V₀ to all of the nodes in V in at most 4 steps, i.e. is there a sequence

V₀;E₁;V₁;E₂;V₂;E₃;V₃; E₄;V₄

which satisfies all of the following:

• V_i is a subset of V for each 0<=i<=4.
• E_i is a subset of E for each 1<=i<=4.
• V₄=V.
• Each edge in E_i has exactly one of its endpoints in V_i-1 (1<=i<=4)
• No two edges in E_i share a common end-point (1<=i<=4)
• V_i=V_i-1union {w: {v,w} in E_i} (1<=i<=4)?

Name: Disjoint Connecting Paths [ND40] 3-4

Input: n-node undirected graph G(V,E); a set of disjoint pairs of nodes {(s₁,t₁);...;(s_k,t_k)}.

Question: Does G contain k mutually node disjoint paths, P_i, with P_i being a path from s_i to t_i?

Comments: Mutually disjoint means that no two paths have any common nodes.

Name: Shortest Weight-Constrained Path [ND30] 3

Input: n-node undirected graph G(V,E); for each edge e in E a positive integer length len(e) and a positive integer weight w(e); specified nodes s and t in V; positive integers K and W.

Question: Is there a path from s to t in G that has both:

• Total weight at most W.
• Total length at most K?

Comments: If all of the edges have the same length or all of the edges have the same weight, then this is simply the normal shortest-path problem for which various efficient algorithms exist, e.g. the Dynamic Programming method of Floyd that is covered in the course. Minimising a single measure, in this context of path lengths, is `easy', but attempting simultaneously to minimise two (or more) distinct measures is not.

Name: Minimum Maximal Matching [GT10] 3

Input: n-node undirected graph G(V,E); positive integers k<=|E|.

Question: Is there a subset, F, of at most k edges from E that forms a maximal matching in G, i.e. no two edges in F have a common endpoint and every edge of G that is not in F has a common endpoint with at least one edge of F?

Name: Partition into Triangles [GT11] 3

Input: (3n)-node undirected graph G(V,E).

Question: Can the nodes of G be partitioned into n disjoint sets - V₁,...,V_n - each of which contains exactly 3 nodes and is such that for each V_i={u_i,v_i,w_i}, all three of the edges {u_i,v_i}, {u_i,w_i} and {v_i,w_i} belong to E?

Name: Partition into Forests [GT14] 3

Input: n-node undirected graph G(V,E); positive integer k<=n

Question: Can the nodes of G be partitioned into t<=k disjoint sets V₁,...,V_t - in such a way that for each V_i (1<=i<=t), the subgraph G_i(V_i,E_i) induced by V_i contains no cycles, i.e. is a forest (set of trees)?

Comments: If G(V,E) is a graph, then the subgraph induced by a subset W of V is the graph H(W,F) whose edges, F, are formed by all the edges in E that connect two nodes in W.

Name: Partition into Cliques [GT15] 3

Input: n-node undirected graph G(V,E); positive integer k<=n

Question: Can the nodes of G be partitioned into t<=k disjoint sets - V₁,...,V_t - in such a way that for each V_i (1<=i<=t), the subgraph G_i(V_i,E_i) induced by V_i is a clique, i.e. a graph in which every pair of nodes is connected by an edge?

Name: Partition into Perfect Matchings [GT16] 3

Input: n-node undirected graph G(V,E); positive integer k<=n

Question: Can the nodes of G be partitioned into t<=k disjoint sets - V₁,...,V_t - in such a way that for each V_i (1<=i<=t), the subgraph G_i(V_i,E_i) induced by V_i is a perfect matching, i.e. a graph in which every node is the endpoint of exactly one edge?

Name: Covering by cliques [GT17] 3

Input: n-node undirected graph G(V,E); positive integer k<=n

Question: Are there t<=k subsets - V₁,...,V_t of V - such that both of the following hold:

• The subgraph G_i(V_i,E_i) of G(V,E) induced by V_i is a clique.
• For each edge {u,v} in E there is some subset V_i that contains both u and v?

Name: Degree-bounded connected subgraph [GT26] 3

Input: n-node undirected graph G(V,E); non-negative integer d<=n; positive integer k<=|E|.

Question: Is there a subset F of the edges in E having size at least k and such that subgraph G(V,F) of G is connected and has no node of degree greater than d?

Name: Uniconnected subgraph [GT30] 3

Input: n-node directed graph G(V,A); positive integer k<=|A|.

Question: Is there a subset B of the edges in A having size at least k and such that the subgraph H(V,B) of G has at most one directed path between any pair of nodes in V?

Name: Minimum k-connected subgraph [GT31] 3

Input: n-node undirected graph G(V,E); positive integers k<=n and B<=|E|.

Question: Is there a subset F of the edges E having size at most B and such that the subgraph H(V,F) of G is k-connected, i.e. remains connected after removing any set W of a most k-1 nodes and their adjacent edges?

Name: Minimum cut linear arrangement [GT44] 3

Input: n-node undirected graph G(V,E); positive integer k.

Question: Is there a one-to-one function f:V->{1,2,...,n} such that for all i, with 1< i< n, the total number of edges {u,v} in E for which f(u)<=i< f(v) is at most k?

Name: Consecutive Sets [SR18] 4

Input: Finite alphabet SIGMA of t symbols; collection C={SIGMA₁,SIGMA₂,...,SIGMA_n} of subsets of SIGMA; positive integer K.

Question: Is there a string, w, (sequence of symbols) over SIGMA such that |w|< =K and for each 1< =i< =n, all of the symbols in SIGMA_i appear in a consecutive block of |SIGMA_i| symbols in the string w?

Comments: N.B. minor typo. in Garey and Johnson, W written instead of w.

Name: Multiple choice matching [GT55] 3

Input: n-node undirected graph G(V,E); partition of E into t disjoint sets - E₁,...,E_t; positive integer k.

Question: Is there a subset F of E having size at least k and satisfying both of the following:

• No two edges in F share a common endpoint.
• F contains at most one edge from each E_i (1<=i<=t)?

Name: Path distinguishers [GT60] 3

Input: n-node directed, acyclic graph G(V,A); specified nodes s and t in V; positive integer k<=|A|.

Question: Is there a subset B of the edges A having size at most k and such that for any pair of distinct paths P and Q from s to t in G, there is an edge in B that is in exactly one of P and Q?

Name: Nestril-Rodl dimension [GT62] 5

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Is there a one-to-one function

f:V-> {( a₁, a₂,...,a_k) : 1 <= a_i<= n }

such that for all pairs of nodes u and v in V, {u,v} is an edge of G if and only if f(u) and f(v) disagree in all k components?

Name: Shortest total path length spanning tree [ND3] 4-5

Input: n-node undirected graph G(V,E); positive integer B.

Question: Is there a spanning tree T(V,F) of G such that the sum over all pairs of nodes u and v of the length of the path between u and v in T is no greater than B?

Name: Induced Path [GT23] 3

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Is there a subset W of the nodes V having size at least k and such that the subgraph H(W,F) of G induced by W is a simple path on |W| nodes?

Name: Bounded Component Spanning Forest [ND10] 3

Input: n-node undirected graph G(V,E); positive integer k<=n.

Question: Can V be partitioned into t disjoint sets - V₁,...,V_t - where t<=k, such that for each i (1<=i<=t) both of the following hold:

• The subgraph H(V_i,E_i) of G induced by V_i is connected.
• The number of nodes in V_i is at most 4.

Name: Maximum subgraph matching [GT50] 3

Input: Directed graphs G(V,A), H(W,B); positive integer k.

Question: Is there a subset R of VxW, i.e. pairs of nodes where one node is from V and one from W, having size at least k and such that for every < u,v> and < x,y> in R the edge (u,x) belongs to A if and only if the edge (v,y) belongs to B?

Name: Numerical 3-dimensional matching [SP16] 3

Input: Disjoint sets W, X, and Y each containing exactly m elements; for each element u of W union X union Y, a positive integer size s(u); a positive integer bound B.

Question: Can the 3m element set W union X union Y be partitioned into m disjoint sets A₁,...,A_m in such a way that:

• Each A_i contains exactly one element from W, exactly one element from X, and exactly one element from Y.
• Each A_i has total size exactly equal to B?

Name: Open Hemisphere [MP6] 4-5

Input: Finite set X of m-tuples of integers; a positive integer k<=|X|.

Question: Is there an m-tuple y of rational numbers such that sum from i=1 to m x_iy_i<> 0 for at least k of the m-tuples in X, x_i (resp. y_i) being the ith component of the m-tuple x (resp. y)?

Name: Largest Common Subgraph [GT49] 3-4

Input: 2 n-node undirected graphs G(V,E), H(W,F); positive integer k.

Question: Do there exist subsets E₁ of the edges E and F₁ of the edges F that satisfy all of the following:

• |E₁|=|F₁|.
• |E₁|>=k, |F₁|>=k.
• The graphs G(V,E₁) and H(W,F₁) are isomorphic, i.e. there is a mapping f between V and W such that {x,y} is an edge in E₁ if and only if {f(x),f(y)} is an edge in F₁?

Name: Clustering [MS9] 3

Input: Finite set X; for each pair of elements x and y in X, a positive integer distance d(x,y); positive integer B.

Question: Is there a partition of X into 3 disjoint sets - X₁,X₂,X₃ - with which: for each set X_i (1<=i<=3), for all pairs x and y in X_i it holds that d(x,y)<=B?

Name: Protein Folding 5

Input: Three positive integers, t, n, and k; a finite alphabet, SIGMA, of t symbols; a string S of length n.

Question: Is there an embedding of S into a two dimensional grid that has a bond-score of at least k? i.e. if S=s₁s₂...s_n, is there a one-to-one function FOLD:{1,...,n}->NxN such that:

• For all 1 <= i< n if FOLD(i)=(x,y) and FOLD (i+1)=(w,z), then either {x=w and |y-z|=1} or {|x-w|=1 and y=z}. (i.e. consecutive members of S are mapped onto adjacent grid co-ordinates).
• The number of pairs {(x,y);(w,z)} of grid positions for which both
• (x,y) and (w,z) are neighbours, (i.e. {x=w and |y-z|=1} or {|x-w|=1 and y=z}).
• FOLD(i)=(x,y) and FOLD(j)=(w,z) (where i and j satisfy 1<=i< j<=n), and s_i=s_j, i.e. the symbols (in SIGMA) mapped onto (x,y) and (w,z) are identical.
• is at least k?

Number: 87

Name: Hamming Centre 3-4

Input: A set S of k binary strings, each of length n; a positive integer r.

Question: Is there an n-bit string y such that for every string x in S, the Hamming distance, H(x,y) is at most r?.

Comments: The Hamming distance, H(x,y), between two binary strings x and y of length n, is the number of bit positions in which x and y have differing values.

This is another recent result not given in Garey and Johnson, its NP-complete classification being given in Frances and Litman (1997).

M. Frances and A. Litman. On Covering Problems of Codes, Theory of Computing Systems, 30, 1997, 113-119

Number: 88

Name: 2-Spanner 3

Input: An undirected graph G(V,E); a positive integer s.

Question: Does G(V,E) contain a 2-spanner with at most s edges, i.e. subset F of the edges E having size at most s and such that for each edge {v,w} in E either {v,w} is in F or (for some node x in V) the edges {v,x} and {x,w} are both in F?

Comments: 2-Spanners (or more generally t-spanners for some positive integer t) are a natural extension of the idea of spanning tree (N.B. A spanner is required neither to be a tree nor, even, a connected graph), and were first considered in the context of problems in communications networks and parallel architectures by Peleg and Ullman (1989). Subsequently, Peleg and Schaffer (1989) showed this problem to be NP-complete, hence its absence from the appendix in Garey and Johnson.

D. Peleg and A.A. Schaffer. Graph Spanners. Jnl. of Graph Theory, 13, (1989), 99-116.

D. Peleg and J.D. Ullman. An Optimal Synchroniser for the Hypercube. SIAM Jnl. on Computing, 18, (1989), 740-747